package com.xmg.day10;

import ch.qos.logback.core.rolling.helper.IntegerTokenConverter;

import java.util.HashMap;

/**
 * 问题描述：走楼梯问题：有一座高度是10级台阶的楼梯，从下往上走，每跨一步只能向上1级或者2级台阶。要求用程序来求出一共有多少种走法。
 *
 * 這是一道入门级的动态递归问题
 *
 * 问题分析：
 *
 * 最有子结构： 最后一步走到第十层有多少种方法？2种：8-》10；9-》10 那么如果走到 8 有x种情况，走到9有y中情况 走到10可以看成x+y
 *
 * 状态转移方程 若用公式表达f(10)=f(9)+f(8) 既 f(n) = f(n-1) + f(n-2)
 *
 * 边界 走到第二层可以走一步，也可以走俩步。即f(2) = 2 第一层只能走一步 f(1) =1
 *
 * 以上是问题建模 解析来是问题求解
 */
public class WalkStairsDemo {
    public static void main(String[] args) {
        System.out.println(walkStairs1(10));
        System.out.println(walkStairs2(10,new HashMap<>()));
        System.out.println(walkStairs3(10));
    }

    /**
     * 第一种思路：用递归的方式
     * @param n n层楼梯
     *这里需要注意一下复杂度问题 这个二叉树长度n-1,节点2^n-1,时间复杂度2^n
     */
    private static int walkStairs1(int n){
        if(n==1) return 1;

        if(n==2) return 2;

        return walkStairs1(n-1)+walkStairs1(n-2);
    }

    /**
     * 第二种思路：还是递归，但是重复的计算几点可以不在计算，叫做备忘录算法 利用map将已经计算过的节点保存
     * @param n n层楼梯
     * @param map 存放中间结果
     * @return 多少种走法
     */
    private static int walkStairs2(int n, HashMap<Integer,Integer> map){
        if(n==1) return 1;

        if(n==2) return 2;

        if(map.containsKey(n)){
            return map.get(n);
        }else{
            int value = walkStairs1(n-1)+walkStairs1(n-2);
            map.put(n,value);
            return value;
        }
    }

    /**
     * 第三种思路：动态规划，每次得到的结果只是上俩次结果的和 时间复杂度o(n) 空间复杂度o（1）
     */
    private static int walkStairs3(int n){
        if(n==1) return 1;

        if(n==2) return 2;

        int temp=0,a=1,b=2;
        for (int i = 3; i <= 10 ; i++) {
            temp = a+b;
            a=b;
            b=temp;
        }
        return temp;
    }


}
